package 我的Java学习_算法基础.day_02;

public class _030_快速设计一个高效的求a的n次幂的算法 {
    public static void main(String[] args) {
        System.out.println(pow0(2,15));
        System.out.println(pow(2,15));
    }
    private static int pow0(int a,int n){
        int res=1;
        for(int i=0;i<n;i++){
            res*=a;
        }
        return res;
    }
    private static int pow(int a,int n){
        if(n==0) return 1;
        int res=a;
        int ex=1;
        while((ex<<1)<=n){      //尝试翻倍
            res*=res;           //翻倍--a^2--a^4---x---a^n 加倍后，逼近或等于a^n
            ex<<=1;             //已经翻倍
        }
        //差n-ex次方没有乘到结果里
        return res*pow(a,n-ex);
    }

}
